import java.util.ArrayList;
import java.util.List;

// 固定窗口+哈希表+维护有效字符
// 有效字符的定义：该字符在窗口中的出现次数不超过 p 中的出现次数。如果超过，那说明该字符不是有效字符
// 进入窗口后，如果 hash2[in - 'a'] <= hash1[in - 'a']，则 count++
// 在出窗口前，如果 hash2[out - 'a'] <= hash1[out - 'a']，则 count--
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ret = new ArrayList<>();
        char[] chars = s.toCharArray();
        char[] charp = p.toCharArray();

        int[] hash1 = new int[26]; //  统计字符串p中每一个字符出现的个数
        for(char ch : charp) hash1[ch - 'a']++;

        int[] hash2 = new int[26]; // 统计窗口中每一个字符出现的个数
        int m = charp.length;

        // count 统计窗口中有效字符的个数，方便和目标字符串p进行比较
        for(int left = 0, right = 0, count = 0; right < chars.length; right++) {
            char in = chars[right];
            hash2[in - 'a']++; // 进窗口
            if(hash2[in - 'a'] <= hash1[in - 'a']) count++; // 维护有效字符个数
            if(right - left + 1 > m) {
                char out = chars[left];
                if(hash2[out - 'a'] <= hash1[out - 'a']) count--; // 维护有效字符个数
                hash2[out - 'a']--; // 出窗口
                left++;
            }
            if(count == m) ret.add(left); // 更新结果
        }
        return ret;
    }
}